package madixin.t111;

import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(root, 1));
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> cur = queue.poll();
            TreeNode curNode = cur.getKey();
            Integer curDepth = cur.getValue();
            if (curNode.left == null && curNode.right == null) {
                return curDepth;
            }
            if (curNode.left != null) {
                queue.add(new Pair<>(curNode.left, curDepth + 1));
            }
            if (curNode.right != null) {
                queue.add(new Pair<>(curNode.right, curDepth + 1));
            }
        }
        return 0;
    }

    /**
     * 递归
     */
    public int minDepth2(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth2(root.left);
        int right = minDepth2(root.right);
        if (left == 0 || right == 0) return left + right + 1;
        return Math.min(left, right) + 1;
    }
}